ハッシュ：リサイズ戦略

再ハッシュの必要性

検索および挿入の望ましい$O(1)$平均ケース性能を保証するためには、負荷係数（$λ = N/M$)は厳密に上限値に制限されなければなりません。ここで$N$は要素数であり、$M$はテーブルの容量です。

もし$λ$が無制限に増加すると、衝突が指数的に増加し、平均時間計算量は$O(N)$に低下します。

一般的な閾値（$λ_max$）：0.70～0.75。

リサイズのプロセス

リサイズには、現在テーブル内にあるすべてのアイテムについてハッシュインデックスを再計算する必要があり、このプロセスは再ハッシュに低下します。

1. 新しい容量の決定：新しい容量$M_new$を設定します。通常、現在の容量の2倍（$M_new = 2M$）とします。これにより、新しい$λ$は臨界閾値の半分になります。
2. テーブルの作成：新しいハッシュテーブル配列（サイズ$M_new$に低下します。
3. アイテムの反復処理：古いテーブル内のすべての$N$既存の要素をループ処理します。
4. 再ハッシュ：各キー$k$について、更新されたモジュラスを使って新しいインデックスを計算します： $$\text{index}' = h(k) \pmod{M_{new}}$$
5. 挿入：アイテムを新しいテーブルの$index′$に低下します。

注：モジュラスが変更されるため、単純に配列をコピーすることは不可能です。すべてのアイテムを再挿入する必要があります。

アモアライズドコスト

なぜリサイズが$O(N)$

リサイズにはすべての$N$要素を処理する必要があり、その操作自体は$O(N)$の時間を要します。これは、$O(1)$挿入の目標を一時的に違反します。

アモアライズド解析

このコストを正当化するためにアモアライズド解析を使用します。テーブルがリサイズごとにサイズを2倍にする（指数成長）場合、高価な$O(N)$コストは、間に続く多くの$O(1)$挿入に分散されます。

任意の1つの挿入の平均コストは、定期的な任意の挿入を考慮に入れても$O(N)$リサイズを含めても$O(1)$に低下します。